package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func main() {
	l3 := ListNode{
		Val:  3,
		Next: nil,
	}

	l2 := ListNode{
		Val:  4,
		Next: &l3,
	}

	l1 := ListNode{
		Val:  2,
		Next: &l2,
	}

	k3 := ListNode{
		Val:  4,
		Next: nil,
	}

	k2 := ListNode{
		Val:  6,
		Next: &k3,
	}

	k1 := ListNode{
		Val:  5,
		Next: &k2,
	}

	printList(&l1)
	printList(&k1)

	r := addTwoNumbers(&l1, &k1)

	printList(r)

}

/*
	这里需要解决的是
	1. 进位
*/
func addTwoNumbers(l1, l2 *ListNode) *ListNode {

	// 1. 先处理个边界
	if l2 == nil {
		return l1
	}

	if l1 == nil {
		return l2
	}

	// 1. 进位符
	carry := 0
	var head *ListNode
	var tail *ListNode

	for l1 != nil || l2 != nil {

		// 2. 初始化0 值
		v1 := 0
		v2 := 0

		if l1 != nil {
			v1 = l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			v2 = l2.Val
			l2 = l2.Next
		}

		// 3. 求和
		sum := v1 + v2 + carry

		// 4. 分别求取当前值和进位
		s := sum % 10
		carry = sum / 10

		// 5 构建链表头尾
		if head == nil {
			head = &ListNode{
				Val: s,
			}
			tail = head
		} else {
			tail.Next = &ListNode{Val: s}
			tail = tail.Next
		}
	}

	// 6 看看最后还需不需要补位
	if carry > 0 {
		tail.Next = &ListNode{Val: carry}
	}

	return head
}

func printList(l *ListNode) {

	for l != nil {
		print(l.Val, " ")
		l = l.Next
	}

	println("")
}
